#include <assert.h>
#include "region.h"
#include "view.h"
#include "visoal.h"

// static objects
static sync_object_t region_sync;
static listnode_t active_rgn_list = LISTNODE_INITIALIZER(active_rgn_list);
static listnode_t lru_rgn_list = LISTNODE_INITIALIZER(lru_rgn_list);

// external functions
int view_getpos(view_t* vi, view_t* ancestor, int* x, int* y);
int view_getpos_delta(view_t* vi, view_t* ancestor, int* deltax, int* deltay);

#define a(r)	((r).left + (r).width - 1)
#define b(r)	((r).top + (r).height - 1)
#define ap(r)	((r)->left + (r)->width - 1)
#define bp(r)	((r)->top + (r)->height - 1)

// this function is not locked
static int _subtract_rect(int x1, int y1, int a1, int b1,
	int x2, int y2, int a2, int b2, void *w,
	void (*proc)(int, int, int, int, void*))
{

#define FIX(x,y,a,b)    \
	do {    \
	register unsigned short tmp;  \
	if ((x) > (a)) { tmp = (x); (x) = (a); (a) = tmp; }  \
	if ((y) > (b)) { tmp = (y); (y) = (b); (b) = tmp; }  \
	}while (0)

#define IN_BOX(x,y,a,b,c,d)	\
	((x) >= (a) && (x) <= (c) && (y) >= (b) && (y) <= (d))

#define INBOX(x,y)      IN_BOX(x,y,x1,y1,a1,b1)

#define FIRST           1
#define SECOND          2
#define THIRD           4
#define FOURTH          8

	unsigned char count = 0,map = 0;

	FIX(x1, y1, a1, b1);
	FIX(x2, y2, a2, b2);

	if (x1 == x2 && y1 == y2 && a1 == a2 && b1 == b2)    /* ????? */
	{
		proc(0, 0, -1, -1, w);
		return 1;
	}

	/* ????????????? */
	if (INBOX(x2,y2))    { count++; map |= FIRST;  }
	if (INBOX(a2,y2))    { count++; map |= SECOND; }
	if (INBOX(x2,b2))    { count++; map |= THIRD;  }
	if (INBOX(a2,b2))    { count++; map |= FOURTH; }

	if (count == 4)      /* ??????? */
	{
		proc(0, 0, -1, -1, w);
		return 1;
	}

	else if (count == 0)
	{
		int y, b;

		/* ??????????? */
		if (x1 > a2 || y1 > b2 || a1 < x2 || b1 < y2)
		{
			proc(x2,y2,a2,b2,w);
			return 1;
		}
		/* ?4?? */
		if (x2 <= a2 && y2 <= y1 - 1)
			proc(x2, y2, a2, y1 - 1, w);

		y = (y2 > y1) ? y2 : y1;
		b = (b2 > b1) ? b1 : b2;
		if (x2 <= x1 - 1 && y <= b)
			proc(x2, y, x1 - 1, b, w);

		if (a1 + 1 <= a2 && y <= b)
			proc(a1 + 1, y, a2, b, w);

		if (x2 <= a2 && b1 + 1 <= b2)
			proc(x2, b1 + 1, a2, b2, w);
		return 1;
	}
	else if (count == 1)
	{
		if (map & FIRST)
		{
			proc(a1 + 1, y2, a2, b1, w);
			proc(x2 , b1 + 1, a2, b2, w);
		}
		else if (map & SECOND)
		{
			proc(x2, y2, x1 - 1, b1, w);
			proc(x2, b1 + 1, a2, b2, w);
		}
		else if (map & THIRD)
		{
			proc(x2, y2, a2, y1 - 1, w);
			proc(a1 + 1, y1, a2, b2, w);
		}
		else if (map & FOURTH)
		{
			proc(x2, y2, a2, y1 - 1, w);
			proc(x2, y1, x1 - 1, b2, w);
		}
		else return 0;
	}
	else if (count == 2)
	{
		if (map & FIRST)
		{
			if (map & SECOND) proc(x2, b1 + 1, a2, b2, w);
			if (map & THIRD)  proc(a1 + 1, y2, a2, b2, w);
		}
		if (map & SECOND)
			if (map & FOURTH) proc(x2, y2, x1 - 1, b2, w);
		if (map & THIRD)
			if (map & FOURTH) proc(x2, y2, a2, y1 - 1, w);
	}
	return 0;

#undef FIX
#undef IN_BOX
#undef INBOX
#undef FIRST
#undef SECOND
#undef THIRD
#undef FOURTH
}

// allocator
view_t* view_alloc(void);
rectlist_node_t* rectlist_node_alloc(void);
void rectlist_node_free(rectlist_node_t* r);

void region_lock(void)
{
	sync_start(&region_sync);
}

void region_unlock(void)
{
	sync_end(&region_sync);
}

static void region_init(region_t* rgn)
{
	if (NULL == rgn)
		return;

	listnode_init(rgn->ownerlist);
	listnode_init(rgn->head[0]);
	listnode_init(rgn->head[1]);

	rgn->rectlist = &rgn->head[0];
	rgn->vi = NULL;
	rgn->rect_count = 0;
	rgn->flags = 0;
}

// create a region
// this function is not locked
region_t* region_create(void)
{
	// reuse rectlist node allocator to create
	// region header. see comments above region_t
	// definition
	region_t* rgn = (region_t*)view_alloc();
	if (NULL == rgn) return NULL;
	region_init(rgn);
	return rgn;
}

// free all rects in the region
// this function is not locked
static void region_release_all_rects(region_t* rgn)
{
	if (NULL == rgn || NULL == rgn->rectlist)
		return;

	while (!listnode_isempty(*(rgn->rectlist)))
	{
		listnode_t* node = rgn->rectlist->next;
		rectlist_node_t* rectnode = list_entry(rectlist_node_t, ownerlist, node);
		listnode_del(*node);
		rectlist_node_free(rectnode);
		--rgn->rect_count;
	}
}

// free a region
void region_free(region_t* rgn)
{
	if (NULL == rgn)
		return;

	region_release_all_rects(rgn);

	if (!listnode_isempty(rgn->ownerlist))
	{
		sync_start(&region_sync);
		listnode_del(rgn->ownerlist);
		sync_end(&region_sync);
	}
	rectlist_node_free((rectlist_node_t*)rgn);
}

// this function is not locked
int region_addrect(region_t* rl, int left, int top, int width, int height)
{
	rectlist_node_t *node;

	if (NULL == rl) return 1;
	if (NULL == rl->rectlist)
		return 2;
	node = rectlist_node_alloc();
	if (NULL == node) return 3;

	node->r.left = left;
	node->r.top = top;
	node->r.width = width;
	node->r.height = height;

	listnode_add(*(rl->rectlist), node->ownerlist);
	++rl->rect_count;
	return 0;
}

int region_getrect(region_t* rl, rect_t* r)
{
	listnode_t* item;
	rectlist_node_t* node;

	if (NULL == rl || NULL == r)
		return 1;
	if (NULL == rl->rectlist)
		return 2;

	sync_start(&region_sync);
	if (region_isempty(*rl))
	{
		sync_end(&region_sync);
		return 3;
	}

	item = rl->rectlist->next;
	listnode_del(*item);
	--rl->rect_count;

	node = list_entry(rectlist_node_t, ownerlist, item);
	*r = node->r;

	sync_end(&region_sync);
	return 0;
}

// this function is not locked
int region_add_view_area(view_t* vi, region_t* rgn)
{
	int l, t;
	assert(NULL != vi && NULL != rgn);

	view_getpos(vi, NULL, &l, &t);
	return region_addrect(rgn, l, t, vi->width, vi->height);
}

static _bool is_intersect1(rect_t* r, int left, int top, int width, int height)
{
	int rc, rd, c, d;
	if (!r || null_rect(*r)) return false;

	rc = r->left + r->width - 1;
	rd = r->top + r->height - 1;
	c = left + width - 1;
	d = top + height - 1;

	if (left > rc || c < r->left)
		return false;
	if (top > rd || d < r->top)
		return false;
	return true;
}

static _bool is_intersect2(rect_t* r1, rect_t* r2)
{
	if (!r1 || !r2 || null_rect(*r2))
		return false;
	return is_intersect1(r1, r2->left, r2->top, r2->width, r2->height);
}

// this function is not locked
static void rect_intersect(rect_t* r, int left, int top, int width, int height)
{
	int rc, rd, c, d;
	if (null_rect(*r)) return;

	rc = r->left + r->width - 1;
	rd = r->top + r->height - 1;
	c = left + width - 1;
	d = top + height - 1;

	if (left > rc || c < r->left)
	{
		invalidate_rect(*r);
		return;
	}
	if (top > rd || d < r->top)
	{
		invalidate_rect(*r);
		return;
	}

	if (r->left < left) r->left = left;
	if (r->top < top) r->top = top;
	if (rc > c) rc = c;
	if (rd > d) rd = d;

	r->width = rc - r->left + 1;
	r->height = rd - r->top + 1;
}

static listnode_t* get_avil_rectlist(region_t* rgn)
{
	listnode_t* ret = &rgn->head[0];
	if (NULL == rgn->rectlist)
		return ret;

	if (rgn->rectlist == &rgn->head[0])
		ret = &rgn->head[1];
	return ret;
}

// this function is not locked
static region_t* region_dup_intersect_rect(region_t* rgn, int left, int top, int width, int height)
{
	listnode_t* item;
	region_t* ret = NULL;
	assert(NULL != rgn && NULL != rgn->rectlist);

	if (width <= 0 || height <= 0)
		return NULL;

	for (item = rgn->rectlist->next; item != rgn->rectlist; item = item->next)
	{
		rect_t tmp;
		rectlist_node_t *node = list_entry(rectlist_node_t, ownerlist, item);
		tmp = node->r;

		rect_intersect(&tmp, left, top, width, height);
		if (!null_rect(tmp))
		{
			if (NULL == ret)
			{
				ret = region_create();
				if (NULL == ret) return NULL;
			}
			region_addrect(ret, tmp.left, tmp.top, tmp.width, tmp.height);
		}
	}

	if (ret && region_isempty(*ret))
	{
		region_free(ret);
		ret = NULL;
	}
	return ret;
}

// this function is not locked
static region_t* region_dup_intersect_view_area(view_t* vi, region_t* rgn)
{
	int l, t;
	assert(NULL != vi && NULL != rgn);

	view_getpos(vi, NULL, &l, &t);
	return region_dup_intersect_rect(rgn, l, t, vi->width, vi->height);
}

// this function is not locked
static void region_intersect_rect(region_t* rgn, int left, int top, int width, int height)
{
	listnode_t* avil_rectlist;
	assert(NULL != rgn && NULL != rgn->rectlist);

	if (width <= 0 || height <= 0)
		region_release_all_rects(rgn);

	avil_rectlist = get_avil_rectlist(rgn);
	while (!listnode_isempty(*(rgn->rectlist)))
	{
		listnode_t* item = rgn->rectlist->next;
		rectlist_node_t *node = list_entry(rectlist_node_t, ownerlist, item);
		listnode_del(*item);

		rect_intersect(&(node->r), left, top, width, height);
		if (null_rect(node->r))
		{
			rectlist_node_free(node);
			--rgn->rect_count;
		}
		else listnode_add(*avil_rectlist, node->ownerlist);
	}
	// reset the rectlist
	rgn->rectlist = avil_rectlist;
}

// this function is not locked
static int region_intersect_view_area(view_t* vi, region_t* rgn)
{
	int l, t;
	assert(NULL != vi && NULL != rgn);

	view_getpos(vi, NULL, &l, &t);
	region_intersect_rect(rgn, l, t, vi->width, vi->height);
	return !region_isempty(*rgn);
}

struct subtract_rect_hdr_data
{
	region_t* target;
	listnode_t* avil_rectlist;
	rectlist_node_t* avil_node;
};

static void region_subtract_rect_handler(int left, int top, int a, int b, void* data)
{
	int width, height;
	rectlist_node_t* node;
	struct subtract_rect_hdr_data* hdr;

	if (a <= left || b <= top)
		return;

	width = a - left + 1;
	height = b - top + 1;

	hdr = (struct subtract_rect_hdr_data*)data;
	node = hdr->avil_node;

	if (node) hdr->avil_node = NULL;
	else node = rectlist_node_alloc();
	if (NULL == node) return;

	node->r.left = left;
	node->r.top = top;
	node->r.width = width;
	node->r.height = height;

	listnode_add(*(hdr->avil_rectlist), node->ownerlist);
	++hdr->target->rect_count;
}

struct subtract_rect_data1
{
	region_t* target;
};

static void subtract_rect_handler(int left, int top, int a, int b, void* data)
{
	int width, height;
	struct subtract_rect_data1* d = (struct subtract_rect_data1*)data;
	if (a <= left || b <= top)
		return;

	if (NULL == d->target)
	{
		d->target = region_create();
		if (NULL == d->target)
			return;
	}

	width = a - left + 1;
	height = b - top + 1;
	region_addrect(d->target, left, top, width, height);
}

// this function is not locked
region_t* subtract_rect(rect_t* r, rect_t* tosub)
{
	struct subtract_rect_data1 d = {NULL};
	if (NULL == r || NULL == tosub)
		return NULL;

	// do subtract
	_subtract_rect(tosub->left, tosub->top, ap(tosub), bp(tosub),
		r->left, r->top, ap(r), bp(r),
		&d, subtract_rect_handler);
	
	if (d.target && region_isempty(*(d.target)))
	{
		region_free(d.target);
		return NULL;
	}
	return d.target;
}

// this function is not locked
void region_subtract_rect(region_t* rgn, int left, int top, int width, int height)
{
	listnode_t *avil_rectlist;
	assert(NULL != rgn && NULL != rgn->rectlist);

	if (width <= 0 || height <= 0)
		return;

	avil_rectlist = get_avil_rectlist(rgn);

	while (!listnode_isempty(*(rgn->rectlist)))
	{
		listnode_t* item = rgn->rectlist->next;
		rectlist_node_t *node = list_entry(rectlist_node_t, ownerlist, item);
		listnode_del(*item);
		--rgn->rect_count;

		// see if the item intersect with the target
		if (is_intersect1(&node->r, left, top, width, height))
		{
			struct subtract_rect_hdr_data d;
			int x1, y1, a1, b1, x2, y2, a2, b2;

			d.target = rgn;
			d.avil_rectlist = avil_rectlist;
			d.avil_node = node;

			x1 = node->r.left;
			y1 = node->r.top;
			a1 = node->r.left + node->r.width - 1;
			b1 = node->r.top + node->r.height - 1;
			x2 = left;
			y2 = top;
			a2 = left + width - 1;
			b2 = top + height - 1;

			// do subtract
			_subtract_rect(x2, y2, a2, b2, x1, y1, a1, b1, &d, region_subtract_rect_handler);

			if (d.avil_node)
				rectlist_node_free(d.avil_node);
		}
		else
		{
			listnode_add(*avil_rectlist, *item);
			++rgn->rect_count;
		}
	}
	// reset the rectlist
	rgn->rectlist = avil_rectlist;
}

// this function is not locked
int region_subtract_view_area(view_t* vi, region_t* rgn)
{
	int l, t;
	assert(NULL != vi && NULL != rgn);

	view_getpos(vi, NULL, &l, &t);
	region_subtract_rect(rgn, l, t, vi->width, vi->height);
	return !region_isempty(*rgn);
}

// this function is not locked
void region_normalize(view_t* vi, region_t* rgn)
{
	int dx, dy;
	listnode_t *n;

	if (NULL == vi || NULL == rgn)
		return;

	if (NULL == rgn->rectlist)
		return;

	view_getpos(vi, NULL, &dx, &dy);
	for (n = rgn->rectlist->next; n != rgn->rectlist; n = n->next)
	{
		rectlist_node_t* rt = list_entry(rectlist_node_t, ownerlist, n);
		rt->r.left -= dx;
		rt->r.top -= dy;
	}
}

struct view_walk
{
	listnode_t ownerlist;
	view_t* vi;
};

// this function is not locked
static void  release_view_walk(listnode_t *head)
{
	while (!listnode_isempty(*head))
	{
		listnode_t* item = head->next;
		struct view_walk* node = list_entry(struct view_walk, ownerlist, item);
		listnode_del(node->ownerlist);
		rectlist_node_free((rectlist_node_t*)node);
	}
}

// this function is not locked
static _bool create_view_walk(view_t* vi, listnode_t* head)
{
	if (NULL == vi)
		return false;

	for (; vi->parent; vi = vi->parent)
	{
		struct view_walk* node = (struct view_walk*)rectlist_node_alloc();
		if (NULL == node)
		{
			release_view_walk(head);
			return false;
		}
		node->vi = vi;
		listnode_add(*head, node->ownerlist);
	}
	return true;
}

// this function is not locked
static view_t* vi_walk_get_and_remove_node(listnode_t* head)
{
	view_t* ret;
	struct view_walk* node;

	if (listnode_isempty(*head))
		return NULL;
	node = list_entry(struct view_walk, ownerlist, head->prev);
	listnode_del(node->ownerlist);
	ret = node->vi;
	rectlist_node_free((rectlist_node_t*)node);
	return ret;
}

// this function is not locked
static view_t* vi_getroot(view_t* vi)
{
	if (NULL == vi) return NULL;
	for (; vi->parent; vi = vi->parent);
	return vi;
}

static void do_invalidate_subtree(view_t* tree, region_t* rgn,
	listnode_t* vi_walk_stack, listnode_t* paint_head, listnode_t* pending_head)
{
	listnode_t *item;
	uint sub_flags = rgn->flags;

	view_t* vitgr = NULL;
	if (rgn->flags & RGN_FLG_PARTIAL)
		vitgr = vi_walk_get_and_remove_node(vi_walk_stack);

	for (item = tree->children.prev;
		item != &(tree->children); item = item->prev)
	{
		region_t* subrgn;
		uint flags = sub_flags;
		view_t* vi = list_entry(view_t, ownerlist, item);
		
		if (sub_flags & RGN_FLG_PARTIAL)
		{
			if (vi == vitgr)
				// all nodes after this one will becomes "full" handling
				sub_flags &= ~RGN_FLG_PARTIAL;
			else if (!region_subtract_view_area(vi, rgn))
				return;
		}
		// else handle full tree
		// below is the common handling
		// see if we need to handle the view
		if (!view_getshow(vi)) continue;

		// calculate region for the view
		subrgn = region_dup_intersect_view_area(vi, rgn);
		if (NULL == subrgn) continue;
		subrgn->vi = vi;
		subrgn->flags = flags;
		listnode_add(*pending_head, subrgn->ownerlist);

		// subtract the view that is already handled
		if (!region_subtract_view_area(vi, rgn))
			return;
	}

	if (!region_isempty(*rgn))
	{
		rgn->vi = tree;
		rgn->flags &= ~RGN_FLG_PARTIAL;
		listnode_add(*paint_head, rgn->ownerlist);
	}
}

_bool invalidate(view_t* vi, region_t* rgn, listnode_t* head)
{
	view_t* root;
	listnode_t vi_walk_head = LISTNODE_INITIALIZER(vi_walk_head);
	listnode_t rgn_pending_head = LISTNODE_INITIALIZER(rgn_pending_head);

	if (NULL == vi || NULL == rgn || NULL == head)
		return false;

	// need lock
	sync_start(&region_sync);

	root = vi_getroot(vi);

	// build the view list via vi
	if (!view_getshow(root) || !create_view_walk(vi, &vi_walk_head))
	{
		sync_end(&region_sync);
		return false;
	}

	// create the first pending object
	if (!region_intersect_view_area(root, rgn))
	{
		release_view_walk(&vi_walk_head);
		sync_end(&region_sync);
		return false;
	}

	rgn->vi = root;
	rgn->flags |= RGN_FLG_PARTIAL;
	listnode_add(rgn_pending_head, rgn->ownerlist);

	// do the real invalidation
	while (!listnode_isempty(rgn_pending_head))
	{
		listnode_t *item = rgn_pending_head.next;
		region_t* r = list_entry(region_t, ownerlist, item);
		listnode_del(r->ownerlist);

		do_invalidate_subtree(r->vi, r, &vi_walk_head,
			head, &rgn_pending_head);
	}

	release_view_walk(&vi_walk_head);
	sync_end(&region_sync);
	return true;
}

void global_init_region(void)
{
	prepare_sync_object(region_sync);
}

void global_destroy_region(void)
{
	release_sync_object(region_sync);
}

/* EOF */
